package q947_removeStones;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    int count = 0;
    List<Integer>[] g = new List[20001];
    boolean[] vis = new boolean[20001];
    /*
    首先是基于建立图的方式来进行 由于题目中设置了对应的范围 所以可以直接使用一个20001的list来代表图
    例如 我们录入 1-1 1-2 2-1 三个点 他们应该属于同一簇
    录入时：
    g[1].add(10002) g[10002].add(1)
    g[1].add(10003) g[10003].add(1)
    g[2].add(10002) g[10002].add(2)
    所以最后应该是g[1] = {10002, 10003} g[2] = {10002} g[10002] = {1, 2} g[10002] = {1}
    dfs时 从s[0] = 1开始 那么vis中将会标记的是 1 10002 2 10003 也就是成功标记了对应的行列上所有点
    所以才能够计算所有的簇

    但是仍然推荐已有的数据结构并查集 即solution3的解法
     */
    public int removeStones(int[][] stones) {
        int n = stones.length;
        for (int i = 0; i < 20001; ++i) {
            g[i] = new ArrayList();
        }
        for (int[] s : stones) {
            g[s[0]].add(s[1] + 10001);
            g[s[1] + 10001].add(s[0]);
        }
        for (int[] s : stones) {
            if (!vis[s[0]]) {
                dfs(s[0]);
                count++;
            }
        }
        return n - count;
    }

    public void dfs(int cur) {
        if (vis[cur]) {
            return;
        }
        vis[cur] = true;
        for (int next : g[cur]) {
            dfs(next);
        }
    }

}
